package com.yiwenup.sorting._06_quick;

import com.yiwenup.sorting.base.Sort;

/**
 * 快速排序：即逐渐将每一个元素转为轴点元素，当所有元素都成为轴点元素时，则排序完成
 * 时间复杂度：最好 - O(nlogn)；最坏 - O(n²)；平均复杂度 - O(nlogn)
 * 空间复杂度：O(nlogn)
 * 稳定性：不稳定
 **/
public class QuickSort<E extends Comparable<E>> extends Sort<E> {
    @Override
    protected void work() {
        sort(0, array.length);
    }

    /**
     * 对 [begin,end) 范围的序列快速排序
     *
     * @param begin 起始位置
     * @param end   结束位置+1
     */
    private void sort(int begin, int end) {
        if (end - begin < 2) return;

        // 确定轴点的位置
        int pivotIndex = pivotIndex(begin, end);
        // 子序列递归快排
        sort(begin, pivotIndex);
        sort(pivotIndex + 1, end);
    }

    /**
     * 确定轴点的位置
     *
     * @param begin 起始位置
     * @param end   结束位置+1
     * @return 轴点的索引
     */
    private int pivotIndex(int begin, int end) {
        // 优化点：随机选择一个元素作为轴点元素，将其与 begin 交换位置
        swap(begin, (int) (begin + Math.random()*(end - begin)));

        // 备份轴点数据
        E tmp = array[begin];

        // 定位到结束位置
        end--;

        // 当 begin 等于 end 时，即指向了轴点位置
        while (begin < end) {
            // 从右往左扫描
            while (begin < end) {
                // 不写等于的目的是为了能够尽可能均匀分割序列
                if (cmp(tmp, array[end]) < 0) {
                    end--;
                } else {
                    array[begin++] = array[end];
                    break;
                }
            }

            // 从左往右扫描
            while (begin < end) {
                // 不写等于的目的是为了能够尽可能均匀分割序列
                if (cmp(tmp, array[begin]) > 0) {
                    begin++;
                } else {
                    array[end--] = array[begin];
                    break;
                }
            }
        }

        // 将轴点元素放入
        array[begin] = tmp;

        return begin;
    }
}
